#include<vector>
#include<bitset>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution {
private:
    vector <vector<int>> ops= { {-1, 0}, { 1,0 }, { 0,-1 }, { 0,1 }};
    int reduce(vector<vector<int>>& grid,vector<vector<bool>>& flags,int i,int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size())
            return 0;
        int maxGold = 0;
        for (auto& op : ops) {
            int new_i = i + op[0];
            int new_j = j + op[1];
            if (new_i < 0 || new_i >= grid.size() || new_j < 0 || new_j >= grid[0].size())
                continue;
            int tmp = 0;
            if (grid[new_i][new_j] > 0 && flags[new_i][new_j]) {
                flags[new_i][new_j] = false;
                tmp =reduce(grid, flags, new_i, new_j);
                flags[new_i][new_j] = true;
                maxGold = max(maxGold, tmp+ grid[new_i][new_j]);
            }
        }
        return maxGold;
    }

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        if (grid.size() < 1) return 0;
        vector<vector<bool>>flags;
        for (int i = 0; i < grid.size(); ++i) {
            flags.emplace_back(grid[i].size(), true);
        }
        int maxGold = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] > 0) {
                    flags[i][j] = false;
                    maxGold = max(maxGold, reduce(grid, flags, i, j) + grid[i][j]);
                    flags[i][j] = true;
                }
            }
        }
        return maxGold;
    }
};